package algorithm.leetcode.medium;

/*
 给你一个升序排列的整数数组 nums ，和一个整数 target 。
 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
 （例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] ）。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/11/2
 */
public class Question33 {

    public static void main(String[] args) {

    }

    public int search(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) {
            return -1;
        }
        if (len == 1) {
            return nums[0] == target ? 0 : -1;
        }
        int left = 0;
        int right = len - 1;
        int mid;
        while (left <= right) {
            mid = (left + right) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // 4 5 6 -1 0 1 2 3  2
            if (nums[0] <= nums[mid]) {
                // 前段部分有序
                if (nums[0] <= target && target < nums[mid]) {
                    // target 在前段部分
                    right = mid - 1;
                } else {
                    // target 在后段部分
                    left = mid + 1;
                }
            } else {
                // 后段部分有序
                if (nums[mid] < target && target <= nums[len - 1]) {
                    // target 在后段部分
                    left = mid + 1;
                } else {
                    // target 在前段部分
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}
